import java.util.Arrays;

/**
 * 大顶堆
 */
public class MaxHeap {
    private int[] tree;
    private int capacity;
    private int size;
    private int growFactor;

    private static final int defaultInitialCapacity = 31;
    private static final int defaultGrowFactor = 2;

    MaxHeap() {
        this(defaultInitialCapacity);
    }
    MaxHeap(int initialCapacity) {
        tree = new int[initialCapacity];
        capacity = initialCapacity;
        size = 0;
        growFactor = defaultGrowFactor;
    }

    public void offer(int value) {
        if (size == capacity) {
            grow();
        }

        tree[size] = value;
        shiftUp(size);
        size++;
    }

    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("Can not poll element from an empty heap!");
        }

        int ret = tree[0];
        tree[0] = tree[--size];
        shiftDown();
        return ret;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Can not peek from an empty heap!");
        }

        return tree[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void setGrowFactor(int growFactor) {
        this.growFactor = growFactor;
    }

    public int getGrowFactor() {
        return growFactor;
    }

    private void shiftUp(int index) {
        int parent = parentIndex(index);
        while (parent >= 0 && tree[parent] < tree[index]) {
            swap(parent, index);
            index = parent;
            parent = parentIndex(parent);
        }
    }

    private void shiftDown() {
        int index = 0;
        int maxChild = leftChildIndex(index);
        while (maxChild < size) {
            //如果右节点存在且值大于左节点，则将较大子节点minChild设为右节点
            if (maxChild + 1 < size && tree[maxChild + 1] > tree[maxChild]) {
                maxChild = maxChild + 1;
            }
            if (tree[maxChild] <= tree[index]) {
                break;
            }
            swap(index, maxChild);
            index = maxChild;
            maxChild = leftChildIndex(maxChild);
        }
    }

    private int parentIndex(int index) {
        return (index - 1) / 2;
    }

    private int leftChildIndex(int index) {
        return index * 2 + 1;
    }

    private void swap(int i, int j) {
        int temp = tree[i];
        tree[i] = tree[j];
        tree[j] = temp;
    }

    private void grow() {
        capacity *= growFactor;
        tree = Arrays.copyOf(tree, capacity);
    }
}
